import java.util.ArrayList;
import java.util.List;

public class SolutionsTest {
    public static void main(String[] args) {
//        int [] a = new int[]{12,-4,16,-5,9,-3,3,8,0};
//        boolean b = canThreePartsEqualSum(a);
//        System.out.println(b);
//        String s1 = "AAAAAA";
//        String s2 = "AAA";
//        SolutionsTest st = new SolutionsTest();
//        String minStr = st.gcdOfStrings(s1,s2);
//        System.out.println(minStr);
        int[] nums = new int[]{1,2,3,2};
        int i = largestRectangleArea(nums);
        System.out.println(i);
    }
//    public static boolean canThreePartsEqualSum(int[] A) {
//        int sum = 0;
//        for(int i = 0;i<A.length;i++){
//            sum+= A[i];
//        }
//        if(sum % 3 == 0 ){
//            int part = sum / 3;
//            int x = -1;
//            int y = -1;
//            int temp = 0;
//            for(int i=0;i<A.length;i++){
//                temp += A[i];
//                if(temp == part){
//                    x = i;
//                    temp = 0;
//                    break;
//                }
//            }
//            for(int i=x+1;i<A.length;i++){
//                temp += A[i];
//                if(temp == part){
//                    y = i;
//                    temp = 0;
//                    break;
//                }
//            }
//            if(x > -1 && y > -1 && y != (A.length-1)){
//                return true;
//            }
//            return false;
//        }
//        return false;
//    }
    public String gcdOfStrings(String str1, String str2) {
        List<String> l1 = getMinStr(str1);
        List<String> l2 = getMinStr(str2);
        List<String> temp = new ArrayList<>(l1);
        l1.removeAll(l2);
        temp.removeAll(l1);
        if(temp.size() > 0){
            int max = 0;
            int index = -1;
            for (int i=0;i<temp.size();i++) {
                int l = temp.get(i).length();
                if(l > max){
                    max = l;
                    index = i;
                }
            }
            return temp.get(index);
        }

        return "";
    }
    public List<String> getMinStr(String s) {
        char[]chars = s.toCharArray();
        List<String> list = new ArrayList<>();
        for(int i=0;i<chars.length;i++){
            String temp = "";
            for(int j=0;j<i+1;j++){
                temp+= chars[j];
            }
            String[] split = s.split(temp);
            if(split.length == 0){
                list.add(temp);
            }
        }
        return list;
    }
    public static int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int area = 0;
        for(int i=0; i<len;i++){
            int left = 0;
            int right = 0;
            int height = heights[i];
            //left
            for(int j=i-1;j>-1;j--){
                if(heights[j] >= height){
                   left++;
                }else{
                    break;
                }
            }
            //right
            for(int k=i+1;k<len;k++){
                if(heights[k] >= height){
                    right++;
                }else{
                    break;
                }
            }
            int tmp = height*(left+right+1);
            if(tmp > area){
                area = tmp;
            }
        }
        return area;
    }
}
